package conclusion;

import java.util.Arrays;
import java.util.Random;

public class Selection {

	/**
	 * O(n + klg k)
	 * @param a
	 * @param left
	 * @param right
	 * @param k
	 */
	public static void partialQuickSortK(int[] a, int left, int right, int k){
		if(left < right){
			Random ram = new Random();
			int pivotIdx = ram.nextInt(right - left + 1) + left;
			int newPivotIdx = partition(a, left, right, pivotIdx);
			partialQuickSortK(a, left, newPivotIdx-1, k);
			if(newPivotIdx < left+k)
				partialQuickSortK(a, newPivotIdx+1, right, k);
		}
	}
	
	
	public static void paritalQuickSortKNoOrder(int[] a, int left, int right, int k){
		if(left < right){
			Random ram = new Random();
			int pivotIdx = ram.nextInt(right - left + 1) + left;
			int newPivotIdx = partition(a, left, right, pivotIdx);
			if(newPivotIdx > left+k)
				paritalQuickSortKNoOrder(a, left, newPivotIdx-1, k);
			
			if(newPivotIdx < left+k)
				paritalQuickSortKNoOrder(a, newPivotIdx+1, right, k);
		}
	}
	
	public static int partition(int[] a, int left, int right, int pivotIdx){
		int temp = a[right];
		a[right] = a[pivotIdx];
		a[pivotIdx] = temp;
		
		int ind = left;
		for(int i = left ; i < right ; i++){
			if(a[i] < a[right]){
				//if(ind != i){
					temp = a[ind];
					a[ind] = a[i];
					a[i] = temp;
				//}
				ind++;
			}
		}
		temp = a[ind];
		a[ind] = a[right];
		a[right] = temp;
		return ind;
	}
	
	public static int[] findSmallestAndSecondSmallest(int[] a, int l, int r){
		int[] res = null;
		if(r - l == 1) {
			res = new int[2];
			if(a[l] < a[r]) {
				res[0] = a[l];
				res[1] = a[r];
			}else{
				res[0] = a[r];
				res[1] = a[l];
			}
		}else{
			res = new int[2];
			int q = (l + r) / 2;
			int[] lres = null; int[] rres = null;
			if(l < q)
				lres = findSmallestAndSecondSmallest(a, l, q);
			if(q+1 < r)
				rres = findSmallestAndSecondSmallest(a, q+1, r);
			if(lres != null && rres != null){
				if(lres[0] < rres[0]){
					res[0] = lres[0];
					res[1] = lres[1] > rres[0] ? rres[0] : lres[1];	
				}else{
					res[0] = rres[0];
					res[1] = lres[0] > rres[1] ? rres[1] : lres[0];	
				}
			}else {
				int[] aa = new int[3];
				if(lres == null) {
					aa[0] = rres[0]; aa[1] = rres[1]; aa[2] = a[l];
				}else{
					aa[0] = lres[0]; aa[1] = lres[1]; aa[2] = a[r];
				}
				Arrays.sort(aa);
				res[0] = aa[0];
				res[1] = aa[1];
			}
		}
		return res;
	}
	
	
	public static void main(String[] args) {
		int[] a = new int[]{4,3,6,8,1,7,2,9,4,11};
		partialQuickSortK(a, 0, 9, 3);
		for(int i : a)
			System.out.print(i + ", ");
		a = new int[]{4,3,6,8,1,7,2,9,4,11};
		paritalQuickSortKNoOrder(a, 0, 9, 3);
		System.out.println();
		for(int i : a)
			System.out.print(i + ", ");
		System.out.println();
		int[] res = findSmallestAndSecondSmallest(a, 0, 9);
		for(int i : res)
			System.out.print(i + ", ");
	}

}
